package 二叉搜索树中的众数;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Solution2 {
    public int[] findMode(TreeNode root) {
        // 中序遍历
        // 通过maxCount记录当前的众数出现的频次
        // 关键步骤就是 更新计数器 + 根据计数器更新结果集

        List<Integer> result = new ArrayList<>();
        int maxCount = 0;
        int nowCount = 0;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode p = root, pre = null;
        while ( p != null || !stack.isEmpty() ){
            if(p != null){
                // left
                stack.push(p);
                p = p.left;
            }else {
                // inorder
                p = stack.pop();
                // 计数
                if (pre==null || pre.val != p.val){
                    nowCount = 1;
                }else {
                    nowCount += 1;
                }
                // 更新结果集
                if (nowCount == maxCount){
                    result.add(p.val);
                }else if (nowCount > maxCount){
                    result.clear();
                    maxCount = nowCount;
                    result.add(p.val);
                }
                // right
                pre = p;
                p = p.right;
            }
        }
        return result.stream().mapToInt(Integer::valueOf).toArray();
    }
}
